The present invention relates to computerized methods of generating graphic images, and more particularly, to a method of displaying or printing lines and curves of arbitrary user specified thicknesses on raster devices.
A display or printer is called a raster device if its image or printed page is made up of a grid of individual picture elements called "pels". When a conventional black and white raster device displays or prints graphic images, such as lines, circles, ellipses and other curves, it does so by blackening those pels in the raster grid that lie closest to the grid location of the line or curve. Until recently, most raster devices have drawn lines or curves that were at most a couple of pels thick. Currently, higher resolution raster devices must be capable of generating lines and curves of arbitrary user specified thickness.
The traditional method of generating a line or curve having a multi-pel thickness is to make a first trace of the line with the thickness of a pel and then to make a succession of retraces of the line or curve, each slightly displaced from the preceding trace. However, this approach rapidly becomes inefficient when the thickness is more than a couple of pels wide. Another conventional method of generating multi-pel thick lines and curves requires the determination of two curves that represent the boundaries and filling black between them. Efficient methods for filling between two curves are well known in the art. The major problem encountered with the boundary and fill method is that the two boundaries are often so mathematically complex that they are not easily determined.
One prior art approach for curve drawing approximates the curve with straight line and/or circular arc segments and determines the boundaries of those segments. The principal drawback of this method is that processing time is significant. Another prior art approach which is discussed in the publication entitled "Curvature Continuity and Offsets for Piecewise Conics" by Gerald Farin approximates the boundaries with curves that are mathematically simpler than the true curves. However, this approach, while fast, results in noticeable errors in many situations. Another prior art approach is discussed by John Hobby in his article entitled "Rasterizing Curves of Constaint Width" published in the the Journal of the Association for Computing Machinery, April 1989, Vol 36, No.2. In Hobby's method, the line or curve to be drawn is defined in terms of a polygon that can be swept to create it. The vertices of the polygon are located on the pel boundaries. This method is also computationally slow.
U.S. Pat. No. 4,601,002 of Rosenthal, granted Jul. 15, 1986, discloses a method of generating lines of variable width on a raster display utilizing an algorithm for generating symbolized lines with so-called "multiply-stroked centerline data."
U.S Pat. No. 4,849,910 of Jacobs et al, granted Jul. 18, 1989, discloses another method of generating a line segment of specific thickness on a raster device. A disk is generated having a diameter which corresponds to the thickness of the line segment. A bit representation of the disk is placed at the start point of the line segment in a bit map memory. A front section of the bit representation of the disk is stored in an intermediate memory. Thereafter, this section of the bit representation of the disk is repeatedly read out of the intermediate memory and placed in the bit memory so that the locations of these sections are related to the line center points of the line segment in consecutive raster lines.
U.S. Pat. No. 4,905,166 of Schuerman, granted Feb. 27, 1990, discloses another method of generating a line part having a given thickness with a raster device, such as a laser printer. Boundaries are determined and a line is drawn based upon generation of a circle and the use of the Bresenham algorithm.